{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Stamping the Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #matrix #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #矩阵 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: possibleToStamp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #用邮票贴满网格图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<code>m x n</code>&nbsp;的二进制矩阵&nbsp;<code>grid</code>&nbsp;，每个格子要么为&nbsp;<code>0</code>&nbsp;（空）要么为&nbsp;<code>1</code>&nbsp;（被占据）。</p>\n",
    "\n",
    "<p>给你邮票的尺寸为&nbsp;<code>stampHeight x stampWidth</code>&nbsp;。我们想将邮票贴进二进制矩阵中，且满足以下&nbsp;<strong>限制</strong>&nbsp;和&nbsp;<strong>要求</strong>&nbsp;：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>覆盖所有 <strong>空</strong>&nbsp;格子。</li>\n",
    "\t<li>不覆盖任何 <strong>被占据&nbsp;</strong>的格子。</li>\n",
    "\t<li>我们可以放入任意数目的邮票。</li>\n",
    "\t<li>邮票可以相互有 <strong>重叠</strong>&nbsp;部分。</li>\n",
    "\t<li>邮票不允许 <strong>旋转</strong>&nbsp;。</li>\n",
    "\t<li>邮票必须完全在矩阵 <strong>内</strong>&nbsp;。</li>\n",
    "</ol>\n",
    "\n",
    "<p>如果在满足上述要求的前提下，可以放入邮票，请返回&nbsp;<code>true</code>&nbsp;，否则返回<i>&nbsp;</i><code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/03/ex1.png\" style=\"width: 180px; height: 237px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]], stampHeight = 4, stampWidth = 3\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>我们放入两个有重叠部分的邮票（图中标号为 1 和 2），它们能覆盖所有与空格子。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/03/ex2.png\" style=\"width: 170px; height: 179px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], stampHeight = 2, stampWidth = 2 \n",
    "<b>输出：</b>false \n",
    "<b>解释：</b>没办法放入邮票覆盖所有的空格子，且邮票不超出网格图以外。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[r].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= m * n &lt;= 2 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>grid[r][c]</code> 要么是&nbsp;<code>0</code>&nbsp;，要么是&nbsp;<code>1</code> 。</li>\n",
    "\t<li><code>1 &lt;= stampHeight, stampWidth &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [stamping-the-grid](https://leetcode.cn/problems/stamping-the-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [stamping-the-grid](https://leetcode.cn/problems/stamping-the-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]]\\n4\\n3', '[[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]\\n2\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m,n =  len(grid),len(grid[0])\n",
    "        Top = [0] * n\n",
    "        Er = [0] * n\n",
    "        if sum([sum(grid[i]) for i in range(m)]) == m*n:return True\n",
    "        if stampHeight > m or stampWidth > n:return False\n",
    "        \n",
    "        for i in range(stampHeight):\n",
    "            for j in range(n):\n",
    "                Er[j] += grid[i][j]\n",
    "        \n",
    "        for i in range(m-stampHeight+1):\n",
    "            S = 0;pos = 0\n",
    "            for x in range(stampWidth):\n",
    "                S += Er[x]\n",
    "            for j in range(n-stampWidth+1):\n",
    "                pos = max(pos,j)\n",
    "                if S and j == n-stampWidth:continue\n",
    "                if S:S -= Er[j];S += Er[j+stampWidth];continue\n",
    "                for k in range(pos,j+stampWidth):\n",
    "                    for l in range(Top[k],i+stampHeight):\n",
    "                        grid[l][k] = 2\n",
    "                    Top[k] = i+stampHeight\n",
    "                pos = j+stampWidth\n",
    "                if j != n-stampWidth:\n",
    "                    S -= Er[j];S += Er[j+stampWidth]\n",
    "            # for x in grid:print(x)\n",
    "            # print(Top,Er)\n",
    "            for x in range(n):\n",
    "                if grid[i][x] == 0:return False\n",
    "            if i == m-stampHeight:continue\n",
    "            for x in range(n):\n",
    "                Er[x] -= 1 if grid[i][x] == 1 else 0\n",
    "                Er[x] += 1 if grid[stampHeight+i][x] == 1 else 0\n",
    "            \n",
    "        for i in range(m-stampHeight+1,m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for r in grid:\n",
    "            pre = -1\n",
    "            for i, j in enumerate(r):\n",
    "                if j == 1:\n",
    "                    if 1 < i - pre <= stampWidth:\n",
    "                        return False\n",
    "                    pre = i\n",
    "            if 1 < n - pre <= stampWidth:\n",
    "                return False\n",
    "        for c in zip(*grid):\n",
    "            pre = -1\n",
    "            for i, j in enumerate(c):\n",
    "                if j == 1:\n",
    "                    if 1 < i - pre <= stampHeight:\n",
    "                        return False\n",
    "                    pre = i\n",
    "            if 1 < m - pre <= stampHeight:\n",
    "                return False\n",
    "\n",
    "        mat = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        # check = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                mat[i][j] = mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1] + grid[i - 1][j - 1]\n",
    "                # check[i][j] = grid[i - 1][j - 1]\n",
    "\n",
    "        def f(i, j):\n",
    "            x, y = i + stampHeight - 1, j + stampWidth - 1\n",
    "            return mat[x + 1][y + 1] + mat[i][j] - mat[i][y + 1] - mat[x + 1][j] == 0\n",
    "\n",
    "        def valid(i, j):\n",
    "            return 0 <= i < m and 0 <= j < n\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    if (not valid(i - 1, j) or grid[i - 1][j] == 1) and (not valid(i, j - 1) or grid[i][j - 1] == 1) and not f(i, j):\n",
    "                        return False\n",
    "                    if (not valid(i - 1, j) or grid[i - 1][j] == 1) and (not valid(i, j + 1) or grid[i][j + 1] == 1) and not f(i, j - stampWidth + 1):\n",
    "                        return False\n",
    "                    if (not valid(i + 1, j) or grid[i + 1][j] == 1) and (not valid(i, j + 1) or grid[i][j + 1] == 1) and not f(i - stampHeight + 1, j - stampWidth + 1):\n",
    "                        return False\n",
    "                    if (not valid(i + 1, j) or grid[i + 1][j] == 1) and (not valid(i, j - 1) or grid[i][j - 1] == 1) and not f(i - stampHeight + 1, j):\n",
    "                        return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "二维前缀和 + 二维差分\n",
    "'''\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        diff = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):  # grid 的二维前缀和\n",
    "                sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + v\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 0:\n",
    "                    x, y = i + stampHeight, j + stampWidth  # 注意这是矩形右下角横纵坐标都 +1 后的位置\n",
    "                    if x <= m and y <= n and sum[x][y] - sum[x][j] - sum[i][y] + sum[i][j] == 0:\n",
    "                        diff[i][j] += 1\n",
    "                        diff[i][y] -= 1\n",
    "                        diff[x][j] -= 1\n",
    "                        diff[x][y] += 1  # 更新二维差分\n",
    "\n",
    "        # 还原二维差分矩阵对应的计数矩阵，这里用滚动数组实现\n",
    "        cnt, pre = [0] * (n + 1), [0] * (n + 1)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                cnt[j + 1] = cnt[j] + pre[j + 1] - pre[j] + diff[i][j]\n",
    "                if cnt[j + 1] == 0 and v == 0:\n",
    "                    return False\n",
    "            cnt, pre = pre, cnt\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        diff = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):  # grid 的二维前缀和\n",
    "                sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + v\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 0:\n",
    "                    x, y = i + stampHeight, j + stampWidth  # 注意这是矩形右下角横纵坐标都 +1 后的位置\n",
    "                    if x <= m and y <= n and sum[x][y] - sum[x][j] - sum[i][y] + sum[i][j] == 0:\n",
    "                        diff[i][j] += 1\n",
    "                        diff[i][y] -= 1\n",
    "                        diff[x][j] -= 1\n",
    "                        diff[x][y] += 1  # 更新二维差分\n",
    "\n",
    "        # 还原二维差分矩阵对应的计数矩阵，这里用滚动数组实现\n",
    "        cnt, pre = [0] * (n + 1), [0] * (n + 1)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                cnt[j + 1] = cnt[j] + pre[j + 1] - pre[j] + diff[i][j]\n",
    "                if cnt[j + 1] == 0 and v == 0:\n",
    "                    return False\n",
    "            cnt, pre = pre, cnt\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sums = [[0]*(n+1) for _ in range(m+1)]\n",
    "        diffs = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for r, row in enumerate(grid, 1):\n",
    "            sRow, lastRow = sums[r], sums[r-1]\n",
    "            last = 0\n",
    "            for c, v in enumerate(row, 1):\n",
    "                sRow[c] = last = last + lastRow[c] - lastRow[c-1] + v\n",
    "            lastRow = sRow\n",
    "        for r in range(stampHeight, m+1):\n",
    "            sRow, lastRow, dRow, dLastRow = sums[r], sums[r-stampHeight], diffs[r], diffs[r-stampHeight]\n",
    "            for c in range(stampWidth, n + 1):\n",
    "                rectSum = sRow[c] - sRow[c-stampWidth] - lastRow[c] + lastRow[c-stampWidth]\n",
    "                if not rectSum:\n",
    "                    dRow[c] += 1\n",
    "                    dRow[c-stampWidth] -= 1\n",
    "                    dLastRow[c] -= 1\n",
    "                    dLastRow[c-stampWidth] += 1\n",
    "        pre, now = [0]*(n+1), [0]*(n+1)\n",
    "        for r, (row, dRow) in enumerate(zip(grid, diffs)):\n",
    "            for c, (v, dv) in enumerate(zip(row, dRow)):\n",
    "                now[c+1] = now[c] + pre[c+1] - pre[c] + dv\n",
    "                if not v and not now[c+1]: return False\n",
    "            pre, now = now, pre\n",
    "        return True\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        diff = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):  # grid 的二维前缀和\n",
    "                sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + v\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 0:\n",
    "                    x, y = i + stampHeight, j + stampWidth  # 注意这是矩形右下角横纵坐标都 +1 后的位置\n",
    "                    if x <= m and y <= n and sum[x][y] - sum[x][j] - sum[i][y] + sum[i][j] == 0:\n",
    "                        diff[i][j] += 1\n",
    "                        diff[i][y] -= 1\n",
    "                        diff[x][j] -= 1\n",
    "                        diff[x][y] += 1  # 更新二维差分\n",
    "\n",
    "        # 还原二维差分矩阵对应的计数矩阵，这里用滚动数组实现\n",
    "        cnt, pre = [0] * (n + 1), [0] * (n + 1)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                cnt[j + 1] = cnt[j] + pre[j + 1] - pre[j] + diff[i][j]\n",
    "                if cnt[j + 1] == 0 and v == 0:\n",
    "                    return False\n",
    "            cnt, pre = pre, cnt\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        diff = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        \n",
    "        # 计算二维前缀和\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + v\n",
    "\n",
    "        # 遍历所有的空位，尝试放置邮票，并更新二维差分矩阵\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 0:\n",
    "                    x, y = i + stampHeight, j + stampWidth\n",
    "                    if x <= m and y <= n and sum[x][y] - sum[x][j] - sum[i][y] + sum[i][j] == 0:\n",
    "                        diff[i][j] += 1\n",
    "                        diff[i][y] -= 1\n",
    "                        diff[x][j] -= 1\n",
    "                        diff[x][y] += 1\n",
    "\n",
    "        # 还原二维差分矩阵对应的计数矩阵\n",
    "        cnt, pre = [0] * (n + 1), [0] * (n + 1)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                cnt[j + 1] = cnt[j] + pre[j + 1] - pre[j] + diff[i][j]\n",
    "                if cnt[j + 1] == 0 and v == 0:\n",
    "                    return False\n",
    "            cnt, pre = pre, cnt\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sum_matrix = [[0] * (n + 1) for _ in range(m + 1)]  # 二维前缀和\n",
    "        diff_matrix = [[0] * (n + 1) for _ in range(m + 1)]  # 二维差分矩阵\n",
    "\n",
    "        # 计算二维前缀和\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                sum_matrix[i + 1][j + 1] = sum_matrix[i + 1][j] + sum_matrix[i][j + 1] - sum_matrix[i][j] + v\n",
    "\n",
    "        # 遍历 grid，将满足条件的位置更新到二维差分矩阵中\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 0:\n",
    "                    x, y = i + stampHeight, j + stampWidth\n",
    "                    # 注意这是矩形右下角横纵坐标都 +1 后的位置\n",
    "                    if x <= m and y <= n and sum_matrix[x][y] - sum_matrix[x][j] - sum_matrix[i][y] + sum_matrix[i][j] == 0:\n",
    "                        diff_matrix[i][j] += 1\n",
    "                        diff_matrix[i][y] -= 1\n",
    "                        diff_matrix[x][j] -= 1\n",
    "                        diff_matrix[x][y] += 1  # 更新二维差分\n",
    "\n",
    "        # 还原二维差分矩阵对应的计数矩阵，这里用滚动数组实现\n",
    "        cnt, pre = [0] * (n + 1), [0] * (n + 1)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                cnt[j + 1] = cnt[j] + pre[j + 1] - pre[j] + diff_matrix[i][j]\n",
    "                if cnt[j + 1] == 0 and v == 0:\n",
    "                    return False\n",
    "            cnt, pre = pre, cnt\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        diff = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):  # grid 的二维前缀和\n",
    "                sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + v\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 0:\n",
    "                    x, y = i + stampHeight, j + stampWidth  # 注意这是矩形右下角横纵坐标都 +1 后的位置\n",
    "                    if x <= m and y <= n and sum[x][y] - sum[x][j] - sum[i][y] + sum[i][j] == 0:\n",
    "                        diff[i][j] += 1\n",
    "                        diff[i][y] -= 1\n",
    "                        diff[x][j] -= 1\n",
    "                        diff[x][y] += 1  # 更新二维差分\n",
    "\n",
    "        # 还原二维差分矩阵对应的计数矩阵，这里用滚动数组实现\n",
    "        cnt, pre = [0] * (n + 1), [0] * (n + 1)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                cnt[j + 1] = cnt[j] + pre[j + 1] - pre[j] + diff[i][j]\n",
    "                if cnt[j + 1] == 0 and v == 0:\n",
    "                    return False\n",
    "            cnt, pre = pre, cnt\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sum = [[0] * (n+1) for _ in range(m+1)]\n",
    "        diff = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + x\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 0:\n",
    "                    x, y = i + stampHeight, j + stampWidth\n",
    "                    if x <= m and y <= n and sum[x][y] - sum[i][y] - sum[x][j] + sum[i][j] == 0:\n",
    "                        diff[i][j] += 1\n",
    "                        diff[i][y] -= 1\n",
    "                        diff[x][j] -= 1\n",
    "                        diff[x][y] += 1\n",
    "\n",
    "        cnt, pre = [0] * (n+1), [0] * (n+1)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                cnt[j+1] = cnt[j] + pre[j+1] - pre[j] + diff[i][j]\n",
    "                if cnt[j+1] == 0 and v == 0:\n",
    "                    return False\n",
    "            cnt, pre = pre, cnt\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sum_matrix = [[0] * (n + 1) for _ in range(m + 1)]  # 二维前缀和\n",
    "        diff_matrix = [[0] * (n + 1) for _ in range(m + 1)]  # 二维差分矩阵\n",
    "\n",
    "        # 计算二维前缀和\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                sum_matrix[i + 1][j + 1] = sum_matrix[i + 1][j] + sum_matrix[i][j + 1] - sum_matrix[i][j] +v\n",
    "\n",
    "        # 遍历 grid，将满足条件的位置更新到二维差分矩阵中\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 0:\n",
    "                    x, y = i + stampHeight, j + stampWidth\n",
    "                    # 注意这是矩形右下角横纵坐标都 +1 后的位置\n",
    "                    if x <= m and y <= n and sum_matrix[x][y] - sum_matrix[x][j] - sum_matrix[i][y] + sum_matrix[i][j] == 0:\n",
    "                        diff_matrix[i][j] += 1\n",
    "                        diff_matrix[i][y] -= 1\n",
    "                        diff_matrix[x][j] -= 1\n",
    "                        diff_matrix[x][y] += 1  # 更新二维差分\n",
    "\n",
    "        # 还原二维差分矩阵对应的计数矩阵，这里用滚动数组实现\n",
    "        cnt, pre = [0] * (n + 1), [0] * (n + 1)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                cnt[j + 1] = cnt[j] + pre[j + 1] - pre[j] + diff_matrix[i][j]\n",
    "                if cnt[j + 1] == 0 and v == 0:\n",
    "                    return False\n",
    "            cnt, pre = pre, cnt\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sum_matrix = [[0] * (n + 1) for _ in range(m + 1)]  # 二维前缀和\n",
    "        diff_matrix = [[0] * (n + 1) for _ in range(m + 1)]  # 二维差分矩阵\n",
    "\n",
    "        # 计算二维前缀和\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                sum_matrix[i + 1][j + 1] = sum_matrix[i + 1][j] + sum_matrix[i][j + 1] - sum_matrix[i][j] + v\n",
    "\n",
    "        # 遍历 grid，将满足条件的位置更新到二维差分矩阵中\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 0:\n",
    "                    x, y = i + stampHeight, j + stampWidth\n",
    "                    # 注意这是矩形右下角横纵坐标都 +1 后的位置\n",
    "                    if x <= m and y <= n and sum_matrix[x][y] - sum_matrix[x][j] - sum_matrix[i][y] + sum_matrix[i][j] == 0:\n",
    "                        diff_matrix[i][j] += 1\n",
    "                        diff_matrix[i][y] -= 1\n",
    "                        diff_matrix[x][j] -= 1\n",
    "                        diff_matrix[x][y] += 1  # 更新二维差分\n",
    "\n",
    "        # 还原二维差分矩阵对应的计数矩阵，这里用滚动数组实现\n",
    "        cnt, pre = [0] * (n + 1), [0] * (n + 1)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                cnt[j + 1] = cnt[j] + pre[j + 1] - pre[j] + diff_matrix[i][j]\n",
    "                if cnt[j + 1] == 0 and v == 0:\n",
    "                    return False\n",
    "            cnt, pre = pre, cnt\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        diff = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):  # grid 的二维前缀和\n",
    "                sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + v\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 0:\n",
    "                    x, y = i + stampHeight, j + stampWidth  # 注意这是矩形右下角横纵坐标都 +1 后的位置\n",
    "                    if x <= m and y <= n and sum[x][y] - sum[x][j] - sum[i][y] + sum[i][j] == 0:\n",
    "                        diff[i][j] += 1\n",
    "                        diff[i][y] -= 1\n",
    "                        diff[x][j] -= 1\n",
    "                        diff[x][y] += 1  # 更新二维差分\n",
    "\n",
    "        # 还原二维差分矩阵对应的计数矩阵，这里用滚动数组实现\n",
    "        cnt, pre = [0] * (n + 1), [0] * (n + 1)\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                cnt[j + 1] = cnt[j] + pre[j + 1] - pre[j] + diff[i][j]\n",
    "                if cnt[j + 1] == 0 and v == 0:\n",
    "                    return False\n",
    "            cnt, pre = pre, cnt\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        s = [[0] * (len(grid[0]) + 2) for _ in range(len(grid) + 2)]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + grid[i][j]    # 求二维前缀和\n",
    "\n",
    "        d = [[0] * (len(grid[0]) + 2) for _ in range(len(grid) + 2)]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 0 and i+stampHeight-1 <=len(grid)-1 and j+stampWidth-1 <=len(grid[0])-1:\n",
    "                    # 用区域内的和判断是否里面的元素都是0\n",
    "                    if s[i+stampHeight][j+stampWidth] - s[i][j+stampWidth] - s[i+stampHeight][j] + s[i][j] == 0:\n",
    "                        self.add(d, i, j, stampHeight, stampWidth)\n",
    "        self.sum(d) # 所有贴邮票操作累加\n",
    "\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] ==0 and d[i + 1][j + 1] == 0:\n",
    "                    return False #如果有空格没有被填上，就返回false\n",
    "        return True\n",
    "\n",
    "    def add(self, d, i, j, stampHeight, stampWidth):\n",
    "        d[i + 1][j + 1] += 1\n",
    "        d[i + stampHeight + 1][j + 1] -= 1\n",
    "        d[i + 1][j + stampWidth + 1] -= 1\n",
    "        d[i + stampHeight + 1][j + stampWidth + 1] += 1\n",
    "\n",
    "    def sum(self, s):\n",
    "        for i in range(1, len(s) - 1):\n",
    "            for j in range(1, len(s[0]) - 1):\n",
    "                s[i][j] += s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        s = [[0] * (len(grid[0]) + 2) for _ in range(len(grid) + 2)]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + grid[i][j]\n",
    "\n",
    "        d = [[0] * (len(grid[0]) + 2) for _ in range(len(grid) + 2)]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 0 and i+stampHeight-1 <=len(grid)-1 and j+stampWidth-1 <=len(grid[0])-1:\n",
    "                    if s[i+stampHeight][j+stampWidth] - s[i][j+stampWidth] - s[i+stampHeight][j] + s[i][j] == 0:\n",
    "                        self.add(d, i, j, stampHeight, stampWidth)\n",
    "        self.sum(d)\n",
    "\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] ==0 and d[i + 1][j + 1] == 0:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "    def add(self, d, i, j, stampHeight, stampWidth):\n",
    "        d[i + 1][j + 1] += 1\n",
    "        d[i + stampHeight + 1][j + 1] -= 1\n",
    "        d[i + 1][j + stampWidth + 1] -= 1\n",
    "        d[i + stampHeight + 1][j + stampWidth + 1] += 1\n",
    "\n",
    "    def sum(self, s):\n",
    "        for i in range(1, len(s) - 1):\n",
    "            for j in range(1, len(s[0]) - 1):\n",
    "                s[i][j] += s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        h, w = stampHeight, stampWidth\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 2D preSum\n",
    "        s = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                s[i][j] = s[i][j-1] + grid[i-1][j-1]\n",
    "        for j in range(1, n+1):\n",
    "            for i in range(1, m+1):\n",
    "                s[i][j] += s[i-1][j]\n",
    "        # 2D difference matrix for stamps\n",
    "        d = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]: continue\n",
    "                if i+h > m or j+w > n: continue\n",
    "                x = s[i+h][j+w] - s[i+h][j] - s[i][j+w] + s[i][j]\n",
    "                if x == 0:\n",
    "                    d[i][j] += 1\n",
    "                    d[i+h][j+w] += 1\n",
    "                    d[i+h][j] -= 1\n",
    "                    d[i][j+w] -= 1\n",
    "        # 2D preSum of d\n",
    "        for i in range(m+1):\n",
    "            for j in range(1, n+1):\n",
    "                d[i][j] += d[i][j-1]\n",
    "        for j in range(n+1):\n",
    "            for i in range(1, m+1):\n",
    "                d[i][j] += d[i-1][j]\n",
    "\n",
    "        return all(d[i][j] + grid[i][j] > 0 for i in range(m) for j in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        Sum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "                for j in range(1, n + 1):\n",
    "                    Sum[i][j] = grid[i - 1][j - 1]\n",
    "        def build(p, row_len, col_len):\n",
    "            for i in range(1, row_len):\n",
    "                for j in range(1, col_len):\n",
    "                    p[i][j] = p[i - 1][j] + p[i][j - 1] + p[i][j] - p[i - 1][j - 1]\n",
    "        build(Sum, m + 1, n + 1)\n",
    "        diff = [[0] * (n + 2) for _ in range(m + 2)]\n",
    "        def sumRegion(a, b, c, d):\n",
    "            return Sum[c][d] - Sum[c][b - 1] - Sum[a - 1][d] + Sum[a - 1][b - 1]\n",
    "        def add(a, b, c, d):\n",
    "            diff[a][b] += 1\n",
    "            diff[a][d + 1] -= 1\n",
    "            diff[c + 1][b] -= 1\n",
    "            diff[c + 1][d + 1] += 1\n",
    "        for i in range(m - stampHeight + 1):\n",
    "            for j in range(n - stampWidth + 1):\n",
    "                if grid[i][j] == 0:\n",
    "                    end_x, end_y = i + stampHeight - 1, j + stampWidth - 1\n",
    "                    if sumRegion(i + 1, j + 1, end_x + 1, end_y + 1) == 0:\n",
    "                        add(i + 1, j + 1, end_x + 1, end_y + 1)\n",
    "        build(diff, m + 2, n + 2)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    if diff[i + 1][j + 1] == 0:\n",
    "                        return False\n",
    "        return True\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid, h, w):\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        \n",
    "        # 创建带有一圈0的前缀和数组\n",
    "        sum_matrix = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                sum_matrix[i + 1][j + 1] = grid[i][j]\n",
    "        \n",
    "        def build(matrix):\n",
    "            for i in range(1, len(matrix)):\n",
    "                for j in range(1, len(matrix[0])):\n",
    "                    matrix[i][j] += matrix[i - 1][j] + matrix[i][j - 1] - matrix[i - 1][j - 1]\n",
    "        \n",
    "        build(sum_matrix)\n",
    "        \n",
    "        # 差分矩阵\n",
    "        diff_matrix = [[0] * (m + 2) for _ in range(n + 2)]\n",
    "        \n",
    "        def sum_region(matrix, a, b, c, d):\n",
    "            return matrix[c][d] - matrix[c][b - 1] - matrix[a - 1][d] + matrix[a - 1][b - 1]\n",
    "        \n",
    "        def add(matrix, a, b, c, d):\n",
    "            matrix[a][b] += 1\n",
    "            matrix[c + 1][d + 1] += 1\n",
    "            matrix[c + 1][b] -= 1\n",
    "            matrix[a][d + 1] -= 1\n",
    "        \n",
    "        # 尝试在每个位置贴邮票\n",
    "        for a in range(1, n - h + 2):\n",
    "            for b in range(1, m - w + 2):\n",
    "                c, d = a + h - 1, b + w - 1\n",
    "                # 如果该区域原始矩阵中的累加和为0，说明可以贴邮票\n",
    "                if sum_region(sum_matrix, a, b, c, d) == 0:\n",
    "                    add(diff_matrix, a, b, c, d)\n",
    "        \n",
    "        build(diff_matrix)\n",
    "        \n",
    "        # 检查所有的位置\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                # 如果原始矩阵为0且差分矩阵为0，说明不能贴邮票\n",
    "                if grid[i][j] == 0 and diff_matrix[i + 1][j + 1] == 0:\n",
    "                    return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ob = [row[:] for row in grid]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                left = ob[i][j - 1] if j > 0 else 0 \n",
    "                up = ob[i - 1][j] if i > 0 else 0 \n",
    "                corner = ob[i - 1][j - 1] if i > 0 and j > 0 else 0\n",
    "                ob[i][j] += left + up - corner\n",
    "        def get_cnt(r1, c1, r2, c2):\n",
    "            left = ob[r2][c1 - 1] if c1 > 0 else 0 \n",
    "            up = ob[r1 - 1][c2] if r1 > 0 else 0 \n",
    "            corner = ob[r1 - 1][c1 - 1] if r1 > 0 and c1 > 0 else 0 \n",
    "            return ob[r2][c2] - left - up + corner > 0 \n",
    "        place = [[0 for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        for i in range(m - stampHeight + 1):\n",
    "            for j in range(n - stampWidth + 1):\n",
    "                x, y = i + stampHeight, j + stampWidth\n",
    "                if get_cnt(i, j, x - 1, y - 1):\n",
    "                    continue\n",
    "                place[i][j] += 1 \n",
    "                place[x][y] += 1 \n",
    "                place[i][y] -= 1 \n",
    "                place[x][j] -= 1 \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                left = place[i][j - 1] if j > 0 else 0 \n",
    "                up = place[i - 1][j] if i > 0 else 0 \n",
    "                corner = place[i - 1][j - 1] if i > 0 and j > 0 else 0\n",
    "                place[i][j] += left + up - corner\n",
    "                if grid[i][j] == 0 and place[i][j] == 0:\n",
    "                    return False \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        diff = [[0 for i in range(len(grid[0])+2)]for j in range(len(grid)+2)]\n",
    "        def add(diff, r1, c1, r2, c2):\n",
    "            diff[r1][c1] += 1\n",
    "            diff[r1][c2+1] += -1\n",
    "            diff[r2+1][c1] += -1\n",
    "            diff[r2+1][c2+1] += 1\n",
    "            # print(diff)\n",
    "        \n",
    "        def build(diff):\n",
    "            for i in range(1, len(diff)-1):\n",
    "                for j in range(1, len(diff[0])-1):\n",
    "                    diff[i][j] += diff[i-1][j]+diff[i][j-1]-diff[i-1][j-1]\n",
    "            # print(diff)\n",
    "        \n",
    "        grid_sum = [[0 for i in range(len(grid[0])+1)]for j in range(len(grid)+1)]\n",
    "        def build_sum(grid, grid_sum):\n",
    "            for i in range(1, len(grid_sum)):\n",
    "                for j in range(1, len(grid_sum[0])):\n",
    "                    grid_sum[i][j] = grid_sum[i-1][j]+grid_sum[i][j-1]-grid_sum[i-1][j-1]+grid[i-1][j-1]\n",
    "\n",
    "        build_sum(grid, grid_sum)\n",
    "\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]==0:\n",
    "                    \n",
    "                    if i+stampHeight<len(grid_sum) and j+stampWidth<len(grid_sum[0]) and grid_sum[i+stampHeight][j+stampWidth]-grid_sum[i][j+stampWidth]-grid_sum[i+stampHeight][j]+grid_sum[i][j]==0:\n",
    "                        # print(i+stampHeight, j+stampWidth)\n",
    "                        add(diff,i+1,j+1,i+stampHeight,j+stampWidth)\n",
    "        \n",
    "        build(diff)\n",
    "        # print(diff)\n",
    "        # print(grid_sum)\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]==0 and diff[i+1][j+1]==0:\n",
    "                    return False\n",
    "\n",
    "        return True\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        s = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        diff = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + grid[i - 1][j - 1]\n",
    "\n",
    "        for i in range(m + 1):\n",
    "            for j in range(n + 1):\n",
    "                x, y = i + stampHeight, j + stampWidth\n",
    "                if x <= m and y <= n and s[x][y] - s[i][y] - s[x][j] + s[i][j] == 0:\n",
    "                    diff[i][j] += 1\n",
    "                    diff[x][j] -= 1\n",
    "                    diff[i][y] -= 1\n",
    "                    diff[x][y] += 1\n",
    "\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + diff[i - 1][j - 1]\n",
    "                if s[i][j] == 0 and grid[i - 1][j - 1] == 0:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        pre = [[0]*(n+1) for _ in range(m+1)]\n",
    "        diff = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i,row in enumerate(grid):\n",
    "            for j,v in enumerate(row):\n",
    "                pre[i+1][j+1] = pre[i][j+1]+pre[i+1][j]-pre[i][j]+v\n",
    "        \n",
    "        for i,row in enumerate(grid):\n",
    "            for j,v in enumerate(row):\n",
    "                if v==0:\n",
    "                    x,y=i+stampHeight,j+stampWidth\n",
    "                    if x<=m and y<=n and pre[x][y]-pre[x][j]-pre[i][y]+pre[i][j] == 0:\n",
    "                        diff[i][j] += 1\n",
    "                        diff[i][y] -= 1\n",
    "                        diff[x][j] -= 1\n",
    "                        diff[x][y] += 1\n",
    "            pass\n",
    "\n",
    "        for i in range(1,m):\n",
    "            diff[i][0] += diff[i-1][0]\n",
    "        for j in range(1,n):\n",
    "            diff[0][j] += diff[0][j-1]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0 and diff[i][j]==0:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        # 初始化二维前缀和矩阵\n",
    "        sums = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        # 构造二维前缀和矩阵，sums[i+1][j+1]记录grid矩阵中右下标为[i][j]的矩阵和（i/j取值0到n-1/m-1）\n",
    "        # 方便后续计算区域和，不用每次都查询再求和\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                sums[i][j] = grid[i-1][j-1] + sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1]\n",
    "        \n",
    "        # 二维差分标记放置邮票位置，为n+2和m+2是为了放在边缘处的值\n",
    "        diff = [[0] * (n+2) for _ in range(m + 2)]\n",
    "        # 找出所有的可以放置邮票的区域\n",
    "        for x_2 in range(stampHeight-1, m):\n",
    "            for y_2 in range(stampWidth-1, n):\n",
    "                x_1 = x_2 - stampHeight\n",
    "                y_1 = y_2 -stampWidth\n",
    "                # 判断该区域内是否是空的（区域内没有1）,和为0代表可以放\n",
    "                if sums[x_2+1][y_2+1] - sums[x_2+1][y_1+1] - sums[x_1+1][y_2+1] + sums[x_1+1][y_1+1] == 0:\n",
    "                    diff[x_1+2][y_1+2] += 1\n",
    "                    diff[x_2+2][y_1+2] -= 1\n",
    "                    diff[x_1+2][y_2+2] -= 1\n",
    "                    diff[x_2+2][y_2+2] += 1\n",
    "        # 构建差分的前缀矩阵,使得被覆盖的地方为1\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] = diff[i][j] + diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]\n",
    "        \n",
    "        for x in range(1, m + 1):\n",
    "            for y in range(1, n + 1):\n",
    "                if grid[x-1][y-1] == 0 and diff[x][y] == 0:\n",
    "                    # 若该位置是空的，且没有被覆盖\n",
    "                    return False\n",
    "        \n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        def build(m):\n",
    "            for i in range(1,len(m)):\n",
    "                for j in range(1,len(m[0])):\n",
    "                    m[i][j] += m[i-1][j]+m[i][j-1]-m[i-1][j-1]\n",
    "        def sumRegion(sum1,a,b,c,d):\n",
    "            return sum1[c][d]-sum1[a-1][d]-sum1[c][b-1]+sum1[a-1][b-1]\n",
    "        def add(diff,a,b,c,d):\n",
    "            diff[a][b] += 1\n",
    "            diff[c+1][d+1] += 1\n",
    "            diff[c+1][b] -= 1 \n",
    "            diff[a][d+1] -= 1\n",
    "\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        sum1 = [[0]*(m+1) for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                sum1[i+1][j+1] = grid[i][j]\n",
    "        build(sum1)\n",
    "        diff = [[0]*(m+2) for _ in range(n+2)]\n",
    "    \n",
    "        \n",
    "        for a in range(1,n+1):\n",
    "            for b in range(1,m+1):\n",
    "                c = a+stampHeight-1\n",
    "                d = b+stampWidth-1\n",
    "                if not (c<=n and d<=m):\n",
    "                    continue\n",
    "                if sumRegion(sum1,a,b,c,d)==0:\n",
    "                    add(diff,a,b,c,d)\n",
    "          \n",
    "        build(diff)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]==0 and diff[i+1][j+1]==0:\n",
    "                    return False\n",
    "        return True            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        #构造二维前缀和\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        sums = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                sums[i+1][j+1] = sums[i][j+1] + sums[i+1][j] - sums[i][j] + grid[i][j]\n",
    "        diff = [[0]*(n+1) for _ in range(m+1)]\n",
    "        #寻找能够插入邮票的位置，要求不越界，区域和为0\n",
    "        for i in range(m):\n",
    "            x = i+stampHeight\n",
    "            if x>m:\n",
    "                break\n",
    "            for j in range(n):\n",
    "                y = j+stampWidth\n",
    "                if y>n:\n",
    "                    break\n",
    "\n",
    "                s = sums[x][y]-sums[x][j] - sums[i][y] + sums[i][j]\n",
    "                if s==0:\n",
    "                    diff[i][j] += 1\n",
    "                    diff[i][y] -= 1\n",
    "                    diff[x][j] -= 1\n",
    "                    diff[x][y] += 1\n",
    "        sums = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                sums[i+1][j+1] = sums[i][j+1] + sums[i+1][j] - sums[i][j] + diff[i][j] \n",
    "                if grid[i][j]==0 and sums[i+1][j+1]==0:\n",
    "                    return False\n",
    "        return True       \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        #构造二维前缀和\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        sums = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                sums[i+1][j+1] = sums[i][j+1] + sums[i+1][j] - sums[i][j] + grid[i][j]\n",
    "        diff = [[0]*(n+1) for _ in range(m+1)]\n",
    "        #寻找能够插入邮票的位置，要求不越界，区域和为0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x = i+stampHeight\n",
    "                y = j+stampWidth\n",
    "                if x<=m and y<=n:\n",
    "                    s = sums[x][y]-sums[x][j] - sums[i][y] + sums[i][j]\n",
    "                    if s==0:\n",
    "                        diff[i][j] += 1\n",
    "                        diff[i][y] -= 1\n",
    "                        diff[x][j] -= 1\n",
    "                        diff[x][y] += 1\n",
    "        sums = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                sums[i+1][j+1] = sums[i][j+1] + sums[i+1][j] - sums[i][j] + diff[i][j] \n",
    "                if grid[i][j]==0 and sums[i+1][j+1]==0:\n",
    "                    return False\n",
    "        return True       \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        s = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        ss = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                s[i][j] = s[i][j + 1] + s[i + 1][j] - s[i + 1][j + 1] + (grid[i][j] == 1)\n",
    "        count = [[0] * (m + stampWidth) for _ in range(n + stampHeight)]\n",
    "        ans = True\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                count[i][j] = count[i - 1][j] + count[i][j - 1] - count[i - 1][j - 1]\n",
    "                if grid[i][j] == 0 and i <= n - stampHeight and j <= m - stampWidth and s[i][j] - s[i + stampHeight][j] - s[i][j + stampWidth] + s[i + stampHeight][j + stampWidth] == 0:\n",
    "                    count[i][j] += 1\n",
    "\n",
    "        ans = True\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 0:\n",
    "                    ss = count[i][j] - count[i - stampHeight][j] - count[i][j - stampWidth] + count[i - stampHeight][j - stampWidth]\n",
    "                    if ss == 0:\n",
    "                        print(ss, i, j, count[i][j], count[i - stampHeight][j], count[i][j - stampWidth], count[i - stampHeight][j - stampWidth])\n",
    "                        ans = False\n",
    "                        break\n",
    "            if not ans: break\n",
    "        \n",
    "        return ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PrefixsumQuery:\n",
    "    def __init__(self, A):\n",
    "        m,n = len(A), len(A[0])\n",
    "        # pre[r][c] == sum(A[:r, :c])\n",
    "        pre = [ [0]*(n+1) for _ in range(m+1) ]\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                pre[r+1][c+1] = A[r][c] + pre[r][c+1] + pre[r+1][c] - pre[r][c]\n",
    "        self.pre = pre\n",
    "\n",
    "    def query(self, r0, c0, r1, c1):\n",
    "        \"\"\" return sum(A[r0:r1+1, c0:c1+1]) \"\"\"\n",
    "        # assert 0<=r0<=r1<m, 0<=c0<=c1<n\n",
    "        return self.pre[r1+1][c1+1] - self.pre[r1+1][c0] - self.pre[r0][c1+1] + self.pre[r0][c0]\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, A: List[List[int]], sh: int, sw: int) -> bool:\n",
    "        m,n=len(A),len(A[0])\n",
    "        preA = PrefixsumQuery(A)\n",
    "        B = [[0]*n for _ in range(m)]\n",
    "        for r in range(m-sh+1):\n",
    "            for c in range(n-sw+1):\n",
    "                if preA.query(r,c,r+sh-1,c+sw-1) == 0:\n",
    "                    B[r][c] = 1\n",
    "        preB = PrefixsumQuery(B)\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if A[r][c] == 0 and preB.query(max(0,r-sh+1),max(0, c-sw+1),r,c)==0:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        pre = [[0]*(n+1) for _ in range(m+1)]\n",
    "        diff = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i,row in enumerate(grid):\n",
    "            for j,v in enumerate(row):\n",
    "                pre[i+1][j+1] = pre[i][j+1]+pre[i+1][j]-pre[i][j]+v\n",
    "        \n",
    "        for i,row in enumerate(grid):\n",
    "            for j,v in enumerate(row):\n",
    "                if v==0:\n",
    "                    x,y=i+stampHeight,j+stampWidth\n",
    "                    if x<=m and y<=n and pre[x][y]-pre[x][j]-pre[i][y]+pre[i][j] == 0:\n",
    "                        diff[i][j] += 1\n",
    "                        diff[i][y] -= 1\n",
    "                        diff[x][j] -= 1\n",
    "                        diff[x][y] += 1\n",
    "            pass\n",
    "\n",
    "        ori = [[0]*n for _ in range(m)]\n",
    "        ori[0][0] = diff[0][0]\n",
    "        for i in range(1,m):\n",
    "            ori[i][0] = diff[i][0] + ori[i-1][0]\n",
    "        for j in range(1,n):\n",
    "            ori[0][j] = diff[0][j] + ori[0][j-1]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                ori[i][j] = diff[i][j] + ori[i-1][j] + ori[i][j-1] - ori[i-1][j-1]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0 and ori[i][j]==0:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PreFixSumMatrix:\n",
    "    def __init__(self, mat):\n",
    "        self.mat = mat\n",
    "        # 二维前缀和\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        self.pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                self.pre[i + 1][j + 1] = self.pre[i][j + 1] + \\\n",
    "                    self.pre[i + 1][j] - self.pre[i][j] + mat[i][j]\n",
    "\n",
    "    def query(self, xa, ya, xb, yb):\n",
    "        # 二维子矩阵和查询，索引从 0 开始，左上角 [xa, ya] 右下角 [xb, yb]\n",
    "        return self.pre[xb + 1][yb + 1] - self.pre[xb +\n",
    "                                                   1][ya] - self.pre[xa][yb + 1] + self.pre[xa][ya]\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], h: int, w: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pre = PreFixSumMatrix(grid)\n",
    "        res = [[0]*n for _ in range(m)]\n",
    "        for i in range(m-h+1):\n",
    "            for j in range(n-w+1):\n",
    "                if pre.query(i, j, i+h-1, j+w-1) == 0:\n",
    "                    res[i][j] = 1\n",
    "        pre2 = PreFixSumMatrix(res)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not grid[i][j]:\n",
    "                    x = i-h+1 if i-h+1>0 else 0\n",
    "                    y = j-w+1 if j-w+1>0 else 0\n",
    "                    if not pre2.query(x, y, i, j):\n",
    "                        return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "\r\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "        pre_sum = [[0] * (n + 1) for _ in range(m + 1)]  # 二维前缀和\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                pre_sum[i + 1][j + 1] = pre_sum[i + 1][j] + pre_sum[i][j + 1] - pre_sum[i][j] + grid[i][j]\r\n",
    "        ss = [[0] * (n + 1) for _ in range(m + 1)]  # 二维差分数组\r\n",
    "        # b[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]\r\n",
    "        for i in range(m - stampHeight + 1):\r\n",
    "            for j in range(n - stampWidth + 1):\r\n",
    "                s = pre_sum[i + stampHeight][j + stampWidth] - pre_sum[i + stampHeight][j] - pre_sum[i][j + stampWidth] + pre_sum[i][j]\r\n",
    "                if s == 0:\r\n",
    "                    ss[i + stampHeight][j + stampWidth] += 1\r\n",
    "                    ss[i][j] += 1\r\n",
    "                    ss[i][j + stampWidth] -= 1\r\n",
    "                    ss[i + stampHeight][j] -= 1\r\n",
    "        p_sum = [[0] * (n + 1) for _ in range(m + 1)]\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                v = p_sum[i + 1][j] + p_sum[i][j + 1] - p_sum[i][j] + ss[i][j]\r\n",
    "                p_sum[i + 1][j + 1] = v\r\n",
    "                if v == 0 and grid[i][j] == 0:\r\n",
    "                    return False\r\n",
    "        return True\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(self, grid: List[List[int]], stampHeight: int, stampWidth: int) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pres = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                pres[i][j] = pres[i - 1][j] + pres[i][j - 1] - pres[i - 1][j - 1] + grid[i - 1][j - 1]\n",
    "\n",
    "        diff = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    x, y = i + stampHeight, j + stampWidth\n",
    "                    if x <= m and y <= n:\n",
    "                        if pres[x][y] - pres[i][y] - pres[x][j] + pres[i][j] == 0:\n",
    "                            diff[i][j] += 1\n",
    "                            diff[i][y] -= 1\n",
    "                            diff[x][j] -= 1\n",
    "                            diff[x][y] += 1\n",
    "        \n",
    "        cur = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    cur[i + 1][j + 1] = cur[i + 1][j] + cur[i][j + 1] - cur[i][j] + diff[i][j]\n",
    "                    if cur[i + 1][j + 1] == 0:\n",
    "                        return False\n",
    "        \n",
    "        return True\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleToStamp(\n",
    "            self, grid: list[list[int]], stampHeight: int, stampWidth: int\n",
    "    ) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        s = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + v\n",
    "\n",
    "        d = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                if v == 0:\n",
    "                    x, y = i + stampHeight, j + stampWidth\n",
    "                    if x <= m and y <= n and s[x][y] - s[x][j] - s[i][y] + s[i][j] == 0:\n",
    "                        d[i][j] += 1\n",
    "                        d[i][y] -= 1\n",
    "                        d[x][j] -= 1\n",
    "                        d[x][y] += 1\n",
    "\n",
    "        cnt = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                cnt[i + 1][j + 1] = cnt[i + 1][j] + cnt[i][j + 1] - cnt[i][j] + d[i][j]\n",
    "                if v == 0 and cnt[i + 1][j + 1] == 0:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "\n",
    "test = Solution()\n",
    "print(test.possibleToStamp([[1, 0, 0, 0],\n",
    "                            [1, 0, 0, 0],\n",
    "                            [1, 0, 0, 0],\n",
    "                            [1, 0, 0, 0],\n",
    "                            [1, 0, 0, 0]]\n",
    "                           , stampHeight=4\n",
    "                           , stampWidth=3))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
